package someTestExcemple.collectionAndMap.map;
import java.util.Comparator;
import java.util.TreeMap;

/**
 * 红黑树（Red-Black Tree）是一种自平衡二叉搜索树（Binary Search Tree，BST），
 * 它通过引入颜色（红色和黑色）标记每个节点，
 * 确保在最坏情况下的时间复杂度仍然是 O(log n)。
 * 红黑树常用于需要高效插入、删除和查找操作的场景，
 * 如 Java 中的 TreeMap 和 TreeSet，以及 Linux 内核中的虚拟内存管理。
 */


/**
 * TreeMap 内部是通过红黑树实现的，
 * 可以让 key 的实现 Comparable 接口或者自定义实现一个 comparator 传入构造函数，
 * 这样塞入的节点就会根据你定义的规则进行排序。
 *
 * 基本特性：
 * 数据结构：TreeMap 基于红黑树实现，红黑树是一种自平衡的二叉查找树，
 * 能够保证基本操作（插入、删除、查找）的时间复杂度为 O(log n)。
 * 键的有序性：TreeMap 中的键是有序的，
 * 默认按自然顺序（键的 Comparable 实现）排序
 * ，也可以通过构造时提供的 Comparator 进行自定义排序。
 * 不允许 null 键：TreeMap 不允许键为 null，但允许值为 null。
 */
public class TreeMapExample {
    public static void main(String[] args) {
        // 使用自然顺序
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        System.out.println("TreeMap: " + treeMap);

        // 使用自定义比较器
        TreeMap<Integer, String> reverseTreeMap = new TreeMap<>(Comparator.reverseOrder());
        reverseTreeMap.put(3, "Three");
        reverseTreeMap.put(1, "One");
        reverseTreeMap.put(2, "Two");
        System.out.println("Reverse TreeMap: " + reverseTreeMap);

        // 获取子映射
        System.out.println("SubMap (1, 3): " + treeMap.subMap(1, 3));

        // 获取前缀映射
        System.out.println("HeadMap (2): " + treeMap.headMap(2));

        // 获取后缀映射 包括第二个
        System.out.println("TailMap (2): " + treeMap.tailMap(2));
    }
}
